package binaryTree;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Class988 {

    String res = "~";
    public String smallestFromLeaf(TreeNode root) {
        if(root == null){
            return res;
        }
        dfs(root, new StringBuilder());
        return res;
    }

    private void dfs(TreeNode root, StringBuilder sb){
        if(root == null){
            return;
        }
        sb.insert(0, (char)('a'+root.val));
        // Update res only at leaf node
        if(root.left == null && root.right == null){
            if(sb.toString().compareTo(res) < 0){
                res = sb.toString();
            }
        }
        dfs(root.left, sb);
        dfs(root.right, sb);
        sb.deleteCharAt(0);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(0);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(2);
        TreeNode treeNode4 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(4);
        TreeNode treeNode6 = new TreeNode(3);
        TreeNode treeNode7 = new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode1.right=treeNode3;
        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        Class988 class988 = new Class988();
        String s = class988.smallestFromLeaf(treeNode1);
        System.out.println(s);


    }
}
